Regular Expressions with Numerical Constraints and Automata with Counters

摘要

Regular expressions with numerical constraints are an extension of regular expressions, allowing to bound numerically the numberof times that a subexpression should be matched. Expressions in thisextension describe the same languages as the usual regular expressions,but are exponentially more succinct.We de ne a class of nite automata with counters and a deterministicsubclass of these. Deterministic nite automata with counters can rec-ognize words in linear time. Furthermore, we describe a subclass of theregular expressions with numerical constraints, a polynomial-time testfor this subclass, and a polynomial-time construction of deterministic nite automata with counters from expressions in the subclass.